package 剑指offer;

public class p14剪绳子I {
    public int cuttingRope(int n) {
        //题目：2 <= n <= 58，且n=2时返回1
        //动态规划
        int[] dp=new int[n+1];
        dp[2]=1;

        for (int i = 3; i <dp.length; i++) {
            for (int j = 1; j <= i/2; j++) {
                //j 代表将 n从第j处分割
                //Math.max(j*(i-j) , j*dp[i-j])
                //j*(i-j)   代表分割后的 第一段长度*剩下长度
                //j*dp[i-j] 代表分割一次后，第一段长度*剩余长度乘积的最大值，剩余长度乘积的最大值前面已经求解过，所以只需要取结果
                dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }

        return dp[n];

    }
}
